package com.tgy.programmer_code_interview_guide._03_binarytree;

import com.tgy.leetcode.TreeNode;

import java.util.Stack;

/**
 * @Author: tgy
 * @Date: 1/29/21 9:32 AM
 *
 * 二叉树中的每一个节点在遍历过程中都要过三次
 *
 * - 第一次路过获取值是前序遍历
 * - 第二次路过获取值是中序遍历
 * - 第三次路过获取值是后序遍历
 *
 */
public class _01_树的遍历 {


    public static void preorderTraversal01(TreeNode root) {

        if (root == null) {

            return;
        }

        Stack<TreeNode> stack = new Stack<>();

        stack.push(root);

        while (!stack.isEmpty()) {

            TreeNode node = stack.pop();

            if (node.right != null) {

                stack.push(node.right);
            }

            if (node.left != null) {

                stack.push(node.left);
            }

            System.out.println(node.val);
        }

    }

    public static void preorderTraversal(TreeNode root) {

        if (root == null) {

            return;
        }

        Stack<TreeNode> stack = new Stack<>();

        TreeNode node = root;
        while (true) {

            while (node != null) {

                if (node.right != null) {
                    stack.push(node.right);
                }
                System.out.println(node.val);
                node = node.left;

            }

            if (stack.isEmpty()) {

                break;
            }

            node = stack.pop();
        }
    }

    /**
     * 中序遍历
     * @param root
     */
    public static void inorderTraversal(TreeNode root) {

        if (root == null) {

            return;
        }

        Stack<TreeNode> stack = new Stack<>();

        TreeNode node = root;
        while (true) {

            while (node != null) {

                stack.push(node);
                node = node.left;
            }

            if (stack.isEmpty()) {
                break;
            }

            node = stack.pop();
            System.out.println(node.val);
            node = node.right;
        }
    }

    public static void postorderTraversal01(TreeNode root) {

        if (root == null) {

            return;
        }

        Stack<TreeNode> stack = new Stack<>();

        Stack<TreeNode> orderStack = new Stack<>();

        stack.push(root);

        while (!stack.isEmpty()) {

            TreeNode node = stack.pop();

            if (node.left != null) {

                stack.push(node.left);
            }

            if (node.right != null) {

                stack.push(node.right);
            }

            orderStack.push(node);
        }


        while (!orderStack.isEmpty()) {

            TreeNode node = orderStack.pop();
            System.out.println(node.val);
        }
    }


    public static void postorderTraversal(TreeNode root) {

        if (root == null) {

            return;
        }

        Stack<TreeNode> stack = new Stack<>();

        stack.push(root);

        TreeNode preNode = null;

        while (!stack.isEmpty()) {

            TreeNode node = stack.peek();


            if ((node.left == null && node.right == null) ||
                    (preNode != null && (node.left == preNode || node.right == preNode))) {

                preNode = node;
                stack.pop();
                System.out.println(node.val);
                // 这里一定要continue，因为下面的已经遍历了。
                continue;
            }

            if (node.right != null) {

                stack.push(node.right);
            }

            if (node.left != null) {

                stack.push(node.left);
            }
        }

    }

    /**
     * mirrors 算法，遍历二叉树，时间O(n),空间为 O(1)
     * @param root
     */
    public static void mirrorsInorderTraversal(TreeNode root) {

        if (root == null) {

            return;
        }

        TreeNode node = root;

        while (node != null) {

            TreeNode leftNode = node.left;

            if (leftNode != null) {

                TreeNode preNode = leftNode;

                while (preNode.right != null && preNode.right != node) {

                    preNode = preNode.right;
                }

                if (preNode.right == null) {

                    System.out.println(node.val);
                    preNode.right = node;
                    node = node.left;
                }else {


                    preNode.right = null;
                    // 左边遍历完了，遍历右边
                    node = node.right;
                }

            }else {

                System.out.println(node.val);
                // 在上一层中为node.right 赋值给中序遍历的下一个节点
                node = node.right;
            }
        }
    }

    public static void main(String[] args) {

        /**
         *
         *           3
         *         /  \
         *       1    5
         *      / \   /
         *     0  2  4
         */
        TreeNode root = new  TreeNode(3);

        root.left = new TreeNode(1);
        root.right = new TreeNode(5);
        root.left.left = new TreeNode(0);
        root.left.right = new TreeNode(2);
        root.right.left = new TreeNode(4);

//        preorderTraversal(root);
//        inorderTraversal(root);
//        postorderTraversal(root);
        mirrorsInorderTraversal(root);
    }
}
